Understanding the fundamental pointer manipulations that enable $O(1)$ insertion and deletion in Linked Lists.
- While the previous slide highlighted that Linked Lists achieve superior modification performance (insertion/deletion in $O(1)$) compared to arrays, this speed is achieved solely through pointer manipulation.
- Understanding the three basic pointer operations is fundamental to mastering LL algorithms, using generic pointers $p$ and $q$.
- 1. Pointer Assignment ($q = p$): The pointer $q$ is made to point to the exact same Node_Structure that $p$ is pointing to. Crucial for maintaining references.
- 2. Pointer Advance ($p = p.next$): The core operation for list Traversal_Highlight. Moves pointer $p$ forward to the next element in the sequence, allowing traversal towards NULL.
- 3. Pointer Relinking ($q.next = p$): The mechanism for structural modification (insertion or deletion). It redirects the next field of the node pointed to by $q$ to now point to the node pointed to by $p$.
- This relinking action physically changes the list's sequence and is visually represented by the Pointer_Relinking_Color (dashed orange line).
Complexity of Basic Pointer Operations
| Operation | Description | Time Complexity |
|---|---|---|
| Assignment | $q = p$ | $O(1)$ |
| Advance | $p = p.next$ | $O(1)$ |
| Relinking | $q.next = p$ | $O(1)$ |